package cn.zyl.demo.java.sort;

/**
 * CountingSort 类说明: 计数排序
 * <p>计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数</p>
 * @author wsz
 * @version v1.0
 * @date 2020-08-13
 */
public class CountingSort extends AbstractArraySortSimple{
    /**
     * 排序接口
     * <pre>
     *     算法步骤:
     *     1.找出原数组中元素值最大的，记为max。
     *     2.创建一个新数组count，其长度是max加1，其元素默认值都为0。
     *     3.遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
     *     4.创建结果数组result，起始索引index。
     *     5.遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。
     *     6.返回结果数组result
     * </pre>
     * @param sourceArray 待排序数组
     * @param order       排序方式，(默认)升序 true；降序 false
     * @return 排序后的数组
     * @throws Exception 异常信息
     */
    @Override
    public Integer[] sort(Integer[] sourceArray, Boolean order) throws Exception {
        int len = sourceArray.length;
        Integer[] arr = copyArray(sourceArray, len);
        start();
        //获取最大值
        int max = arr[0];
        for (int val:arr) {
            if(max < val){max = val;addOne();}
        }
        //临时数组，长度等于max
        int bucketLen = max + N_1;
        int[] bucket = new int[bucketLen];
        //计数统计
        for (int val:arr) { bucket[val]++;addOne(); }
        //生成排序后的数组
        int sortedIndex = N_0;
        if(order){
            //升序
            for(int i = 0; i < bucketLen; i++){
                while (bucket[i] > N_0){
                    addOne();
                    arr[sortedIndex++] = i;
                    bucket[i]--;
                }
            }
        }else {
            for(int i = bucketLen-1; i >= 0; i--){
                while (bucket[i] > N_0){
                    addOne();
                    arr[sortedIndex++] = i;
                    bucket[i]--;
                }
            }
        }
        end();
        return arr;
    }
    public static void main(String[] args) {
        int len = 15,max=100;
        //待排序数组初始化
        Integer[] arr = randomArray(len,max);
        AbstractArraySortSimple sort = new CountingSort();
        try {
            System.out.println("升序操作");
            printArray(sort.sort(arr, true));
            System.out.println("降序降序");
            printArray(sort.sort(arr, false));
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}
